package io.gimo.study.design_pattern.factory.abstract_factory.product;


import io.gimo.study.design_pattern.factory.abstract_factory.Sortor;

import java.util.Arrays;

public class MergeSortor implements Sortor {

	@Override
	public void sort(int[] target) {
		sort(target,0,target.length-1);
		System.out.println(Arrays.toString(target));
	}

	private void sort(int[] target, int left, int right) {
		if(left<right){
            int middle = (left+right)/2;
            //对左边进行递归
            sort(target, left, middle);
            //对右边进行递归
            sort(target, middle+1, right);
            //合并
            merge(target,left,middle,right);
        }
	}

	private void merge(int[] target, int left, int middle, int right) {
		int[] tmpArr = new int[target.length];
        //右边的起始位置
        int mid = middle+1;
        int tmp = left;
        int third = left;
        while(left<=middle && mid<=right){
            //从两个数组中选取较小的数放入中间数组
            if(target[left]<=target[mid]){
                tmpArr[third++] = target[left++];
            }else{
                tmpArr[third++] = target[mid++];
            }
        }
        //将剩余的部分放入中间数组
        while(left<=middle){
            tmpArr[third++] = target[left++];
        }
        while(mid<=right){
            tmpArr[third++] = target[mid++];
        }
        //将中间数组复制回原数组
        while(tmp<=right){
        	target[tmp] = tmpArr[tmp++];
        }
		
	}

}
